package course.p4_list.s5_RelaxList;

import java.lang.reflect.Array;
import java.util.AbstractList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.io.Serializable;
import java.util.ConcurrentModificationException;


/**
 * 松散链表定义类
 * @param <E>
 */
public class RelaxList<E> extends AbstractList<E> implements List<E>, Serializable {

    /**
     * 链表中块的容量
     */
    private final int RelaxNodeCapacity;

    /**
     * 链表元素总个数
     */
    private int size = 0;

    /**
     *  链表第一个块
     */
    private final Node firstRelaxNode;

    /**
     *  链表最后一个块
     */
    private Node lastRelaxNode;

    private static final long serialVersionUID = -674052309103045211L;

    /**
     * 松散链表带参构造方法
     * @param RelaxNodeCapacity 指定松散链表的块大小,这里必须不小于8
     * @throws IllegalArgumentException 如果定义的块大小小于8，抛出异常
     */
    public RelaxList(int RelaxNodeCapacity) throws IllegalArgumentException {
        if (RelaxNodeCapacity < 8) {
            throw new IllegalArgumentException("RelaxNodeCapacity < 8");
        }
        this.RelaxNodeCapacity = RelaxNodeCapacity;
        firstRelaxNode = new Node(RelaxNodeCapacity);
        lastRelaxNode = firstRelaxNode;
    }

    /**
     * 松散链表无参构造方法，默认构造出块大小为16的松散链表
     */
    public RelaxList() {
        this(16);
    }

    /**
     * 将指定的元素添加到链表的末尾
     * @param e 指定元素
     * @return 返回true
     */
    @Override
    public boolean add(E e) {
        insertIntoRelaxNode(lastRelaxNode, lastRelaxNode.numElements, e);
        return true;
    }

    /**
     * 返回链表大小
     * @return int
     */
    public int size() {
        return size;
    }


    /**
     * 判断链表是否为空
     * @return boolean
     */
    @Override
    public boolean isEmpty() {
        return (size == 0);
    }


    /**
     * 查询链表是否包含指定元素，如果包含返回true
     * @param o 指定元素
     * @return boolean
     */
    @Override
    public boolean contains(Object o) {
        return (indexOf(o) != -1);
    }

    /**
     * 查找链表中是否存在指定元素
     * @param o 指定元素
     * @return 元素所在的位置
     */
    @Override
    public int indexOf(Object o) {
        int index = 0;
        Node RelaxNode = firstRelaxNode;
        if (o == null) {
            while (RelaxNode != null) {
                for (int ptr = 0; ptr < RelaxNode.numElements; ptr++) {
                    if (RelaxNode.elements[ptr] == null) {
                        return index + ptr;
                    }
                }
                index += RelaxNode.numElements;
                RelaxNode = RelaxNode.next;
            }
        } else {
            while (RelaxNode != null) {
                for (int ptr = 0; ptr < RelaxNode.numElements; ptr++) {
                    if (o.equals(RelaxNode.elements[ptr])) {
                        return index + ptr;
                    }
                }
                index += RelaxNode.numElements;
                RelaxNode = RelaxNode.next;
            }
        }
        return -1;
    }


    /**
     * 获得松散链表的迭代器
     * @return 迭代器
     */
    @Override
    public Iterator<E> iterator() {
        return new RelaxIterator(firstRelaxNode, 0, 0);
    }


    /**
     * 将链表元素集合转化为Object数组返回
     * @return 数组
     */
    @Override
    public Object[] toArray() {
        Object[] array = new Object[size];
        int p = 0;
        for (Node RelaxNode = firstRelaxNode; RelaxNode != null; RelaxNode = RelaxNode.next) {
            for (int i = 0; i < RelaxNode.numElements; i++) {
                array[p] = RelaxNode.elements[i];
                p++;
            }
        }
        return array;
    }

    /**
     * 返回指定类型的数组
     * @param a 指定类型的空数组
     * @param <T> 泛型变量
     * @return 类型数组对象
     */
    @Override
    @SuppressWarnings({ "unchecked" })
    public <T> T[] toArray(T[] a) {
        //如果传入的数组大小小于链表大小，则重新新建一个数组
        if (a.length < size) {
            //新建一个指定类型的数组
            a = (T[])Array.newInstance(a.getClass().getComponentType(),size);
        }
        Object[] result = a;
        int p = 0;
        for (Node RelaxNode = firstRelaxNode; RelaxNode != null; RelaxNode = RelaxNode.next) {
            for (int i = 0; i < RelaxNode.numElements; i++) {
                result[p] = RelaxNode.elements[i];
                p++;
            }
        }
        return a;
    }

    /**
     * 删除链表中指定元素
     * 如果成功删除返回true 如果不存在此元素返回false
     * @param o 指向元素对象
     * @return 是否成功删除
     */
    @Override
    public boolean remove(Object o) {
        int index = 0;
        Node RelaxNode = firstRelaxNode;
        if (o == null) {
            while (RelaxNode != null) {
                for (int ptr = 0; ptr < RelaxNode.numElements; ptr++) {
                    if (RelaxNode.elements[ptr] == null) {
                        removeFromRelaxNode(RelaxNode, ptr);
                        return true;
                    }
                }
                index += RelaxNode.numElements;
                RelaxNode = RelaxNode.next;
            }
        } else {
            while (RelaxNode != null) {
                for (int ptr = 0; ptr < RelaxNode.numElements; ptr++) {
                    if (o.equals(RelaxNode.elements[ptr])) {
                        removeFromRelaxNode(RelaxNode, ptr);
                        return true;
                    }
                }
                index += RelaxNode.numElements;
                RelaxNode = RelaxNode.next;
            }
        }
        return false;
    }


    /**
     * 判断链表是否包含入参集合的所有元素
     * @param c 集合
     * @return 全包含返回true 不全包含返回false
     */
    @Override
    public boolean containsAll(Collection<?> c) {
        if (c == null) {
            throw new NullPointerException();
        }
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 将指定集合中所有元素加入到链表中
     * @param c 指向集合
     * @return 成功返回true 失败返回false
     */
    @Override
    public boolean addAll(Collection<? extends E> c) {
        if (c == null) {
            throw new NullPointerException();
        }
        boolean changed = false;
        for (E e : c) {
            add(e);
            changed = true;
        }
        return changed;
    }


    /**
     * 从链表中删除集合c中所有元素
     * @param c 集合c
     * @return 成功标志
     */
    @Override
    public boolean removeAll(Collection<?> c) {
        if (c == null) {
            throw new NullPointerException();
        }
        Iterator<?> it = c.iterator();
        boolean changed = false;
        while (it.hasNext()) {
            if (remove(it.next())) {
                changed = true;
            }
        }
        return changed;
    }


    /**
     *删除链表中除包含在集合c中的其他所有元素，仅保留c中有的
     * @param c 指定集合c
     * @return 成功标志
     */
    @Override
    public boolean retainAll(Collection<?> c) {
        if (c == null) {
            throw new NullPointerException();
        }
        boolean changed = false;
        for (Node RelaxNode = firstRelaxNode; RelaxNode != null; RelaxNode = RelaxNode.next) {
            for (int i = 0; i < RelaxNode.numElements; i++) {
                if (!c.contains(RelaxNode.elements[i])) {
                    removeFromRelaxNode(RelaxNode, i);
                    i--;
                    changed = true;
                }
            }
        }
        return changed;
    }

    /**
     *清空链表，只剩一个头，且头中元素都清除了
     */
    @Override
    public void clear() {

        Node RelaxNode = firstRelaxNode.next;
        while (RelaxNode != null) {
            Node next = RelaxNode.next;
            RelaxNode.next = null;
            RelaxNode.previous = null;
            RelaxNode.elements = null;
            RelaxNode = next;
        }
        lastRelaxNode = firstRelaxNode;
        for (int ptr = 0; ptr < firstRelaxNode.numElements; ptr++) {
            firstRelaxNode.elements[ptr] = null;
        }
        firstRelaxNode.numElements = 0;
        firstRelaxNode.next = null;
        size = 0;

    }

    /**
     *获得指定位置的元素
     * @param index 指定位置
     * @return 返回指定位置元素
     * @throws IndexOutOfBoundsException 如果传入的位置不合法，抛出异常
     */
    @SuppressWarnings({ "unchecked" })
    public E get(int index) throws IndexOutOfBoundsException {

        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node RelaxNode;
        int p = 0;
        if (size - index > index) {
            RelaxNode = firstRelaxNode;
            while (p <= index - RelaxNode.numElements) {
                p += RelaxNode.numElements;
                RelaxNode = RelaxNode.next;
            }
        } else {
            RelaxNode = lastRelaxNode;
            p = size;
            while ((p -= RelaxNode.numElements) > index) {
                RelaxNode = RelaxNode.previous;
            }
        }
        return (E) RelaxNode.elements[index - p];

    }


    /**
     *更新指定位置的元素
     * @param index 指定位置
     * @param element 指定元素
     * @return 返回此位置的原来的元素
     */
    @Override
    @SuppressWarnings({ "unchecked" })
    public E set(int index, E element) {

        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        E el = null;
        Node RelaxNode;
        int p = 0;
        if (size - index > index) {
            RelaxNode = firstRelaxNode;
            while (p <= index - RelaxNode.numElements) {
                p += RelaxNode.numElements;
                RelaxNode = RelaxNode.next;
            }
        } else {
            RelaxNode = lastRelaxNode;
            p = size;
            while ((p -= RelaxNode.numElements) > index) {
                RelaxNode = RelaxNode.previous;
            }
        }
        el = (E) RelaxNode.elements[index - p];
        RelaxNode.elements[index - p] = element;
        return el;

    }


    /**
     *在指定位置添加元素
     * @param index 指定位置
     * @param element 指定元素
     * @throws IndexOutOfBoundsException
     */
    @Override
    public void add(int index, E element) throws IndexOutOfBoundsException {

        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        Node RelaxNode;
        int p = 0;
        if (size - index > index) {
            RelaxNode = firstRelaxNode;
            while (p <= index - RelaxNode.numElements) {
                p += RelaxNode.numElements;
                RelaxNode = RelaxNode.next;
            }
        } else {
            RelaxNode = lastRelaxNode;
            p = size;
            while ((p -= RelaxNode.numElements) > index) {
                RelaxNode = RelaxNode.previous;
            }
        }
        insertIntoRelaxNode(RelaxNode, index - p, element);

    }


    /**
     *删除指定位置的元素
     * @param index 指定位置
     * @return 返回删除之前这个位置的元素
     * @throws IndexOutOfBoundsException 如果位置不合法，抛出异常
     */
    @Override
    @SuppressWarnings({"unchecked"})
    public E remove(int index) throws IndexOutOfBoundsException {

        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        E element = null;
        Node RelaxNode;
        int p = 0;
        if (size - index > index) {
            RelaxNode = firstRelaxNode;
            while (p <= index - RelaxNode.numElements) {
                p += RelaxNode.numElements;
                RelaxNode = RelaxNode.next;
            }
        } else {
            RelaxNode = lastRelaxNode;
            p = size;
            while ((p -= RelaxNode.numElements) > index) {
                RelaxNode = RelaxNode.previous;
            }
        }
        element = (E) RelaxNode.elements[index - p];
        removeFromRelaxNode(RelaxNode, index - p);
        return element;

    }

    /**
     *找出指定元素在链表中最后出现的位置索引
     * @param o 指定元素
     * @return 返回位置索引
     */
    @Override
    public int lastIndexOf(Object o) {
        int index = size;
        Node RelaxNode = lastRelaxNode;
        if (o == null) {
            while (RelaxNode != null) {
                index -= RelaxNode.numElements;
                for (int i = RelaxNode.numElements - 1; i >= 0; i--) {
                    if (RelaxNode.elements[i] == null) {
                        return (index + i);
                    }
                }
                RelaxNode = RelaxNode.previous;
            }
        } else {
            while (RelaxNode != null) {
                index -= RelaxNode.numElements;
                for (int i = RelaxNode.numElements - 1; i >= 0; i--) {
                    if (o.equals(RelaxNode.elements[i])) {
                        return (index + i);
                    }
                }
                RelaxNode = RelaxNode.previous;
            }
        }
        return -1;
    }


    /**
     *得到这个链表的迭代器
     * @return 链表迭代器
     */
    @Override
    public ListIterator<E> listIterator() {
        return new RelaxIterator(firstRelaxNode, 0, 0);
    }

    /**
     *得到从指定位置后的松散链表迭代器
     * @param index 指定位置
     * @return 链表迭代器
     */
    @Override
    public ListIterator<E> listIterator(int index) {

        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        Node RelaxNode;
        int p = 0;
        if (size - index > index) {
            RelaxNode = firstRelaxNode;
            while (p <= index - RelaxNode.numElements) {
                p += RelaxNode.numElements;
                RelaxNode = RelaxNode.next;
            }
        } else {
            RelaxNode = lastRelaxNode;
            p = size;
            while ((p -= RelaxNode.numElements) > index) {
                RelaxNode = RelaxNode.previous;
            }
        }
        return new RelaxIterator(RelaxNode, index - p, index);

    }

    /**
     * 向指定块的指定位置插入指定元素
     * @param RelaxNode 指定块
     * @param ptr 指定位置
     * @param element 指定元素
     */
    private void insertIntoRelaxNode(Node RelaxNode, int ptr, E element) {
        //如果这个块满了
        if (RelaxNode.numElements == RelaxNodeCapacity) {
            // 创建一个新块
            Node newRelaxNode = new Node(RelaxNodeCapacity);
            // 将一半的元素移到新块中
            int elementsToMove = RelaxNodeCapacity / 2;
            int startIndex = RelaxNodeCapacity - elementsToMove;
            int i;
            for (i = 0; i < elementsToMove; i++) {
                newRelaxNode.elements[i] = RelaxNode.elements[startIndex + i];
                RelaxNode.elements[startIndex + i] = null;
            }
            RelaxNode.numElements -= elementsToMove;
            newRelaxNode.numElements = elementsToMove;
            // 将新块插入到链表指定块后面
            newRelaxNode.next = RelaxNode.next;
            newRelaxNode.previous = RelaxNode;
            if (RelaxNode.next != null) {
                RelaxNode.next.previous = newRelaxNode;
            }
            RelaxNode.next = newRelaxNode;

            if (RelaxNode == lastRelaxNode) {
                lastRelaxNode = newRelaxNode;
            }
            // 如果插入位置大于原始块的实际元素数,此元素应该插入新块中
            if (ptr > RelaxNode.numElements) {
                RelaxNode = newRelaxNode;
                ptr -= RelaxNode.numElements;
            }
        }
        //由于块是数组是实现，所以插入位置后的元素都后移一位
        for (int i = RelaxNode.numElements; i > ptr; i--) {
            RelaxNode.elements[i] = RelaxNode.elements[i-1];
        }
        //执行插入操作
        RelaxNode.elements[ptr] = element;
        RelaxNode.numElements++;
        //维护链表大小
        size++;
        modCount++;
    }

    /**
     * 删除块指定位置的元素
     * @param RelaxNode 指定块
     * @param ptr 指定位置
     */
    private void removeFromRelaxNode(Node RelaxNode, int ptr) {
        RelaxNode.numElements--;
        //后面的元素向前移动一位
        for (int i = ptr; i < RelaxNode.numElements; i++) {
            RelaxNode.elements[i] = RelaxNode.elements[i + 1];
        }
        RelaxNode.elements[RelaxNode.numElements] = null;
        //如果此块不是最后一个块且此块和它的下一个块的元素总数小于块大小，则进行块合并操作
        if (RelaxNode.next != null && (RelaxNode.next.numElements + RelaxNode.numElements) <= RelaxNodeCapacity) {
            mergeWithNextRelaxNode(RelaxNode);
            //如果此块不是最后一个块且它和上一个块的元素总数小于块大小，则进行合并操作
        } else if (RelaxNode.previous != null && (RelaxNode.previous.numElements + RelaxNode.numElements) <= RelaxNodeCapacity) {
            mergeWithNextRelaxNode(RelaxNode.previous);
        }
        size--;
        modCount++;

    }

    /**
     * 块合并操作：将指定块和它的下一个块进行合并
     * @param RelaxNode 指定块
     */
    private void mergeWithNextRelaxNode(Node RelaxNode) {
        Node next = RelaxNode.next;
        for (int i = 0; i < next.numElements; i++) {
            RelaxNode.elements[RelaxNode.numElements + i] = next.elements[i];
            next.elements[i] = null;
        }
        //块的元素总数变量维护
        RelaxNode.numElements += next.numElements;
        if (next.next != null) {
            next.next.previous = RelaxNode;
        }
        RelaxNode.next = next.next;
        if (next == lastRelaxNode) {
            lastRelaxNode = RelaxNode;
        }
    }

    /**
     * 松散链表迭代器
     */
    private class RelaxIterator implements ListIterator<E> {

        Node currentRelaxNode;
        int ptr;
        int index;

        private final int expectedModCount = modCount;

        RelaxIterator(Node RelaxNode, int ptr, int index) {

            this.currentRelaxNode = RelaxNode;
            this.ptr = ptr;
            this.index = index;

        }

        //下一个位置
        @Override
        public boolean hasNext() {
            return (index < size - 1);
        }


        @Override
        @SuppressWarnings({"unchecked"})
        public E next() {

            ptr++;
            if (ptr >= currentRelaxNode.numElements) {
                if (currentRelaxNode.next != null) {
                    currentRelaxNode = currentRelaxNode.next;
                    ptr = 0;
                } else {
                    throw new NoSuchElementException();
                }
            }
            index++;
            checkForModification();
            return (E) currentRelaxNode.elements[ptr];

        }

        //判断
        @Override
        public boolean hasPrevious() {

            return (index > 0);

        }

        @Override
        @SuppressWarnings({"unchecked"})
        public E previous() {

            ptr--;
            if (ptr < 0) {
                if (currentRelaxNode.previous != null) {
                    currentRelaxNode = currentRelaxNode.previous;
                    ptr = currentRelaxNode.numElements - 1;
                } else {
                    throw new NoSuchElementException();
                }
            }
            index--;
            checkForModification();
            return (E) currentRelaxNode.elements[ptr];

        }

        @Override
        public int nextIndex() {

            return (index + 1);

        }

        @Override
        public int previousIndex() {

            return (index - 1);

        }

        @Override
        public void remove() {

            checkForModification();
            removeFromRelaxNode(currentRelaxNode, ptr);

        }

        @Override
        public void set(E e) {

            checkForModification();
            currentRelaxNode.elements[ptr] = e;

        }

        @Override
        public void add(E e) {

            checkForModification();
            insertIntoRelaxNode(currentRelaxNode, ptr + 1, e);

        }

        private void checkForModification() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }
    }

}
